package com.smh;

import org.junit.jupiter.api.Test;

import java.util.ArrayDeque;
import java.util.List;

/**
 * @author shiminghui
 * @date 2025/3/14 15:55
 * @description: TODO
 */
public class _042_图 {

    @Test
    public void test1() {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");

        v1.setEdges(List.of(new Edge(v1, v2, 1), new Edge(v1, v3, 1)));
        v2.setEdges(List.of(new Edge(v2, v4, 1)));
        v3.setEdges(List.of(new Edge(v3, v4, 1)));
        v4.setEdges(null);

//        dfs(v1);
        System.out.println("---------------------------------");
//        dfs2(v1);
        bfs(v1);
    }

    /**
     * 广度优先遍历,非递归
     *
     * @param v
     */
    public void bfs(Vertex v) {
        if (v == null) {
            return;
        }
        ArrayDeque<Vertex> queue = new ArrayDeque<>();
        queue.addLast(v);
        while (!queue.isEmpty()) {
            Vertex vertex = queue.removeFirst();
            if (!vertex.isVisited()) {
                vertex.setVisited(true);
                System.out.println(vertex);
                if (vertex.getEdges() == null) {
                    continue;
                }
                for (Edge edge : vertex.getEdges()) {
                    queue.addLast(edge.getTo());
                }
            }
        }
    }

    /**
     * 广度优先遍历,递归
     *
     * @param v
     */
    public void bfs2(Vertex v) {
    }


    /**
     * 深度优先遍历,递归
     *
     * @param v
     */
    public void dfs(Vertex v) {
        if (v == null) {
            return;
        }
        if (!v.isVisited()) {
            v.setVisited(true);
            System.out.println(v);
        }
        if (v.getEdges() == null) { // 防止空指针
            return;
        }
        for (Edge edge : v.getEdges()) {
            Vertex to = edge.getTo();
            if (!to.isVisited()) {
                dfs(to);
            }
        }
    }

    /**
     * 深度优先遍历,非递归
     *
     * @param v
     */
    public void dfs2(Vertex v) {
        ArrayDeque<Vertex> stack = new ArrayDeque<>();
        stack.addLast(v);
        while (!stack.isEmpty()) {
            Vertex vertex = stack.removeLast();
            if (!vertex.isVisited()) {
                vertex.setVisited(true);
                System.out.println(vertex);
                List<Edge> edges = vertex.getEdges();
                if (edges == null) {
                    continue;
                }
                for (Edge edge : vertex.getEdges()) {
                    stack.addLast(edge.getTo());
                }
            }
        }
    }


    /**
     * 边类
     */
    private class Edge {
        private Vertex from;
        private Vertex to;
        private int weight;

        public Edge(Vertex from, Vertex to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        public Vertex getFrom() {
            return from;
        }

        public void setFrom(Vertex from) {
            this.from = from;
        }

        public Vertex getTo() {
            return to;
        }

        public void setTo(Vertex to) {
            this.to = to;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }


    /**
     * 顶点类
     */
    private class Vertex {
        private String name;
        private List<Edge> edges;
        private boolean visited = false;

        public Vertex(String name, List<Edge> edges) {
            this.name = name;
            this.edges = edges;
        }

        public Vertex(String name) {
            this.name = name;
        }

        public boolean isVisited() {
            return visited;
        }

        public void setVisited(boolean visited) {
            this.visited = visited;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public List<Edge> getEdges() {
            return edges;
        }

        public void setEdges(List<Edge> edges) {
            this.edges = edges;
        }

        public String toString() {
            return name;
        }
    }
}
